package com.yangzhe.algorithm.c042;

// 可以用r、e、d三种字符拼接字符串，如果拼出来的字符串中
// 有且仅有1个长度>=2的回文子串，那么这个字符串定义为"好串"
// 返回长度为n的所有可能的字符串中，好串有多少个
// 结果对 1000000007 取模， 1 <= n <= 10^9
// 示例：
// n = 1, 输出0
// n = 2, 输出3
// n = 3, 输出18
public class Code04_RedPalindromeGoodStrings {

    // 暴力方法
    // 为了观察规律
    // 好串个数 num = f(i, n, path)
    public static int num1(int n) {
        String[] path = new String[n];
        return f(0, n, path);
    }

    public static int f(int i, int n, String[] path) {
        if (i < n) {
            path[i] = "r";
            int r = f(i + 1, n, path);
            path[i] = "e";
            int e = f(i + 1, n, path);
            path[i] = "d";
            int d = f(i + 1, n, path);

            return r + e + d;
        } else {

            // 路径中的回文计数
            int count = 0;
            // 从 0 - 1..0 - 2..0 - n是否回文
            // 从 1 - 2..1 - 3..1 - n是否回文
            for (int start = 0; start < n; start++) {
                for (int end = start + 1; end < n; end++) {
                    if (is(path, start, end)) {
                        count++;
                    }

                    if (count > 1) {
                        return 0;
                    }
                }
            }
            // 回文个数为1 的才满足条件
            return count == 1 ? 1 : 0;
        }
    }

    /**
     * 判断是否是回文
     *
     * @param path  要判断的字符数组
     * @param start 开始位置
     * @param end   结束位置                     j
     * @return
     */
    public static boolean is(String[] path, int start, int end) {
        while (start <= end) {
            // 存在不相等则不是回文
            if (!path[start].equals(path[end])) {
                return false;
            }
            start++;
            end--;
        }

        // 全部相等就是回文
        return true;
    }


    /**
     * 打表 0是1 2 是3     3是18
     * 4是30 之后，之后每次都 + 6
     *
     * @param n
     * @return
     */
    public static int num2(int n) {
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            return 3;
        } else if (n == 3) {
            return 18;
        } else {
            return 30 + (n - 4) * 6;
        }
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            System.out.println("长度为" + i + ", 答案:" + num1(i));
            System.out.println("长度为" + i + ", 答案:" + num2(i));
        }
    }

}
